package __1背包

/**
原题链接:
https://leetcode.cn/problems/last-stone-weight-ii/

代码随想录 动态规划章节
1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

代码随想录 动态规划章节
1049. 最后一块石头的重量 Ⅱ
有一堆石头, 用整数数组 stones表示. 其中 stones[i]表示第i块石头的重量.
每一回和, 从中选出任意两块石头, 然后将他们一起粉碎. 鸡舍石头的重量分别为x和y, 且x<=y, 那么粉碎的可能结果如下:

示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：
输入：stones = [31,26,33,21,40]
输出：5

思路:
例如[2,7.4,1,8,1]这个数组,
总和为23, 取一半值为11,
那么能不能凑出重量为11的石头堆呢?  8,2,1 能够凑出重量为11的石头堆  另一堆石头重量为12
11和12的石头堆相撞, 剩下的重量为1

总体思路就是:
	尽量分出两个重量相似的石头堆, 这样相撞之后剩下的石头重量才能最小
	因为数组和sum是已知的, target = sum/2, 此题可以转换为如何尽量凑成重量为 target重量的石头堆

	这样本题和分割等和子集,就很相似了,
	区别在于:
		分割子集等和子集如果能分割成功, 就return true, 否则return false
		本题则是尽量凑, 凑不成也没关系, 两堆石头相撞也是最小值

	这样就成功转换为了背包问题, 每个物品只能用一次, 依旧是0-1背包问题

总体思路就是:
	尽量分出两个重量相似的石头堆, 这样相撞之后剩下的石头重量才能最小
	因为数组和sum是一致的, target = sum/2, 此题可以转换为如何尽量凑成重量为 target重量的石头堆
	这样本题和分割等和子集, 就很相似了
	区别在于:
		分割子集等和子集如果能分割成功, 就return true, 否则return false
		本题则是尽量凑, 凑不成也没关系, 两堆石头相撞也是最小值

一. dp[j]的含义:
	本题中, 石头的重量也是它的价值, 所以装满dp[11]的背包的最大价值,就是求装满容量为11的背包的最大重量

二. 递推公式
	dp[j] = max(dp[j], dp[j-stone[i]] + stone[i])

三. dp数组初始化
	dp[0] = 0  		0容量背包, 只能装0价值的物品
	非0下标也初始化为0即可

四. 遍历顺序
	先遍历物品, 再遍历背包
	for (i=0; i<stones.size(); i++)
		for (j=target; j>=stones[i]; j--)

最终获取dp[target]中的值, 表示尽量凑target大的重量, 即使凑不够也没关系, 已经是尽量凑的最接近的值了
可得:
	第一堆石头: dp[target]
	第二堆石头: sum - dp[target]

因为dp[target]是sum/2的值, 除2是向下取整的, 一定小于sum-target
那么要求的最小剩余石头值为: sum-dp[target] - dp[target]
*/

func lastStoneWeightII(stones []int) int {

	//求累加和
	sum := 0

	for _, v := range stones {
		sum += v
	}

	//求target
	target := sum / 2

	//声明dp数组
	dp := make([]int, target+1)

	//填充dp数组
	for i := 0; i < len(stones); i++ {
		for j := target; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}

	//返回总和-两倍dp[target]容量即可
	return sum - 2*dp[target]
}
